package com.mo.list;

/**
 * @ClassName NodeUtil
 * @Description 链表操作
 * @Author Administrator
 * @Date 2021/8/3
 * @Version 1.0
 */
public class NodeUtil {

    /**
     * 建立链表的数据(头插法)
     *
     * @param a
     * @return 头节点
     */
    public static Node headInsert(int[] a) {
        Node p;
        //头节点
        Node h = new Node();
        h.next = null;
        for (int i = 0; i < a.length; i++) {
            p = new Node(a[i]);
            //插入到头节点
            p.next = h.next;
            //头节点转换为h，继续插入
            h.next = p;
        }
        return h.next;
    }

    /**
     * 建立链表的数据（尾插法）
     *
     * @param a
     * @return 尾节点
     */
    public static Node tailInsert(int[] a) {
        Node p, t;
        //头节点
        Node h = new Node();
        h.next = null;
        t = h;
        for (int i = 0; i < a.length; i++) {
            p = new Node(a[i]);
            //插入到尾节点
            p.next = null;
            //p放入尾部
            t.next = p;
            //尾节点转换为t，继续插入
            t = p;
        }
        return t;
    }

    /**
     * 计算链表的长度(头节点不为空)
     *
     * @return 长度
     */
    public static int size(Node h) {
        Node p;
        p = h;
        int i = 1;
        while (p.next != null) {
            i++;
            p = p.next;
        }
        return i;
    }

    /**
     * 尾插元素
     *
     * @param a 插入数据
     * @param p 插入的坐标
     * @return 新链表
     */
    public static Node insertElementAfter(int a, Node p) {
        Node h = new Node(a);
        //尾节点后移
        h.next = p.next;
        //作为新的尾节点
        p.next = h;

        return p;
    }

    /**
     * 头插元素
     *
     * @param a 数据
     * @param b 坐标(b个元素之前)
     * @param h 头节点
     * @return 新元素
     */
    public static Node insertElementAt(int a, int b, Node h) {
        Node p = new Node(a);
        Node s;
        int i = 0;
        s = h;
        //遍历插入的坐标
        while (s != null & i < b - 1) {
            s = s.next;
            i++;
        }
        //存在位置，直接插入
        if (s != null) {
            p.next = s.next;
            s.next = p;
            return s;
        } else {
            return null;
        }


    }

    /**
     * 删除固定节点
     *
     * @param p 删除的节点的前驱节点
     * @return 新链表
     */
    public static Node delete(Node p) {
        Node h;
        if (p.next != null) {
            //连接为后继
            h = p.next;
            //连接删除的后继节点
            p.next = h.next;
            //释放空间
            h = null;
        }
        return p;
    }

    /**
     * 查找值对应的节点
     *
     * @param h 链表
     * @param a 数值
     * @return 节点
     */
    public static Node search(Node h, int a) {
        Node p = h;
        while (p.next != null && p.data != a) {
            p = p.next;
        }
        return p;
    }

    public static Node searchOffset(Node h, int a) {
        Node p = h;
        int i = 0;
        while (p.next != null && a - i > 0) {
            p = p.next;
            i++;
        }
        return p;
    }
}
